This invention relates to interleaving and is particularly concerned with interleaving systems and methods suited for Turbo and Turbo-like forward-error-correcting codes, by using golden section increments.
Interleaving is a key component of many digital communications systems involving forward error correction (FEC) coding. This is especially true for channels characterized by fading, multipath, and impulse noise, for example. A second example is the class of magnetic recording channels where bursts of errors are caused by defects in the recording media. Interleaving, or permuting, of the transmitted elements, provides time diversity for the FEC scheme being employed. An element is used herein to refer to any symbol, sample, digit, or a binary digit (bit). Interleaving spreads out the corrupted portions of the signal and makes it easier for the FEC scheme to correct the associated errors. Conventionally, the interleaving strategy is only weakly linked to the FEC scheme being employed. An exception is the case of concatenated FEC schemes using concatenated Viterbi and Reed-Solomon decoders. The interleaver is placed between the two FEC encoders to help spread out error bursts and the depth of interleaving is directly linked to the error correction capability of the inner (Viterbi) decoder. More recently, however, interleavers have become a more integral part of the coding and decoding strategy itself. Such is the case for Turbo and Turbo-like codes, where the interleaver forms an integral part of the coding scheme. The problem of finding optimal interleavers for such schemes is really a code design problem, and is an on-going area of research.
Claude Berrou obtained U.S. Pat. No. 4,446,747 entitled: xe2x80x9cError-correction coding method with at least two systematic convolutional codings in parallel, corresponding iterative decoding method, decoding module and decoderxe2x80x9d. This patent describes essentially the same Turbo-code presented by Berrou et al. in their paper xe2x80x9cNear Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codesxe2x80x9d, published in the Proceedings of ICC""93, Geneva, Switzerland, pp. 1064-1070, May, 1993. The Turbo code presented, is a rate xc2xd binary code that provided performance within 0.5 dB of the BPSK capacity limit at a BER of 10xe2x88x925, when using an interleaver block size of 65,536. This result is also only 0.7 dB from the more general Shannon capacity limit. The encoder consists of two rate xc2xd recursive systematic convolutional (RSC) encoders operating in parallel with the information binary digits (bits) interleaved between the two encoders as shown in FIG. 1. Without puncturing, and with rate xc2xd constituent codes, the overall code rate is ⅓. This is because the systematic information bits only need to be sent once. Other code rates can be achieved as required by puncturing the parity bits c1k and c2k. In this configuration, the job of the interleaver is to spread error bursts that occur in one code throughout the other code so that there is a higher probability of correcting unreliable information.
More recently Berrou, and Glavieux provided more discussion of the coding and decoding of Turbo codes in their paper xe2x80x9cNear Optimum Error Correcting Coding and Decoding: Turbo-Codesxe2x80x9d, published in the IEEE Trans. on Conm., Vol. 44, No. 10, October 1996.
FIG. 2 illustrates one approach to Turbo decoding, based on maximum a posteriori (MAP) decoding algorithm derived by Bahl et al their paper xe2x80x9cOptimal Decoding of Linear Codes for Minimizing Symbol Error Ratexe2x80x9d, published in IEEE Trans. on Inform. Theory, Vol. IT-20, pp. 284-287, March 1974. The MAP decoder is implemented in the log domain, so the log-MAP algorithm is used. The Turbo decoder uses an iterative process where the de-interleaved output vector of the second log-MAP decoder L2, is fed back to the input of the first log-MAP decoder after the first iteration. The storage vector to the second log-MAP decoder must be interleaved using the same interleaver used in the Turbo encoder. Likewise, the output from the second log-MAP decoder must be de-interleaved before being fed back to the input of the first log-MAP decoder. Decisions can be made either at the output of the first log-MAP decoder or the de-interleaved output of the second log-MAP decoder. It is the convention that one Turbo decoding iteration be defined as two log-MAP decoding operations as shown in FIG. 2.
Interleaving is a key component of any Turbo encoder and decoder, as already shown in FIGS. 1 and 2. Although some form of random or pseudo-random interleaving is usually recommended for Turbo-codes, it has been found that simple structured interleavers can also offer excellent performance, especially for short data blocks on the order of a few hundred bits. Examples of structured prior art interleavers include relative prime interleavers, convolutional interleavers, helical interleaver and Lxc3x97M matrix (or block) interleavers using L rows and M columns. Lxc3x97M matrix interleavers are usually implemented by writing into the rows and reading out of the columns, or vice versa. The rows and/or columns are sometimes read in and/or out in a permuted order. This permuted order is often implemented using a relative prime number. That is, the row or column index can be generated using modulo arithmetic where the index increment and row or column lengths are relative prime numbers. With L or M equal to 1, this type of interleaver simply becomes a one-dimensional relative prime interleaver.
In U.S. Pat. No. 5,056,105, Darmon et al refer to relative prime interleavers which seem to offer some advantages over conventional Lxc3x97M matrix interleavers. In a relative prime interleaver, the n""th digit (element) of the interleaved vector is read out of the original vector using the index s+np, modulo N, where s is an integer starting index and p is an integer index increment. The starting index s is usually set to 0 but can be any index. The increment p must be relative prime to the block size N to ensure that each element is read out once and only once.
One problem with prior art interleavers is that they are usually designed to provide a specific interleaving depth. This is fine if each burst of errors never exceeds the interleaver depth, but it is wasteful if the interleaver is over-designed (too long) and error bursts are much shorter than the interleaver depth. For example, a simple 10xc3x9710 matrix interleaver has an interleaving depth of 10 elements. If a burst of 10 errors occurs, the de-interleaver will optimally spread these 10 errors throughout the block of 100 elements. If the error burst is 11 elements long, however, then two errors will again be adjacent. If the error burst is only 2-elements long then these 2 errors will only be spaced 10 elements apart after de-interleaving, but they could have been spaced much farther apart if it was known that only two errors were present. For example, a 2xc3x9750 matrix interleaver would have spaced these two errors 50 elements apart. Of course this interleaver is not good for longer bursts of errors. In practice, most channels usually generate error events of random length, and the average length can be time varying, as well as unknown. This makes it very difficult to design optimum interleaving strategies using the above-mentioned prior art methods.
It is also desirable for an interleaving strategy for Turbo-codes to spread xe2x80x9cerror burstsxe2x80x9d from one component decoder throughout the data block for the other component decoder. One measure of how good a particular burst of elements has been spread by an interleaver is the minimum difference between the interleaved indexes of the original burst of elements considered. The problem is that error bursts can start anywhere and are random in length. The best interleaver for one burst length is not necessarily the best interleaver for another burst length. What is sought is an interleaving strategy that is good for any error burst length.
An object of this invention is to provide an improved interleaver with a tendency to maximally spread the error-bursts generated by an error-burst channel or decoder, independent of the error-burst length.
It is another object of this invention to use golden section increments to achieve desirable spreading properties.
In addressing these objects, the invention makes use of the golden section, which is easy to compute for any block size, and is unique for that block size. In other words, the block size uniquely defines a golden section increment in accordance with this invention, without having to perform a time consuming search for the best increment value. A number of interleaver embodiments, based on this golden section increment, are provided by this invention. The term interleaver is also used to refer to a de-interleaver.
With this invention, there is no concept of interleaver depth and no need to design the interleaver for a particular channel type or for a worst case error-burst length. For Turbo-codes it is also beneficial to obtain good spreading for elements r apart, where r is the repetition period of the feedback polynomial in the RSC encoder, as well as for adjacent elements. As an example, a good binary, rate xc2xd, RSC encoder has a repetition period of r=2mxe2x88x921, where k and m=kxe2x88x921 are the constraint length and memory, respectively, of the RSC encoder.
In accordance with an aspect of this invention there is provided an interleaving system for rearranging a stream of N input elements into a stream of N output elements, said interleaving system comprising:
(a) an element memory;
(b) an indexer for generating a sequence of input indexes and a sequence of output indexes, wherein at least one of said sequences of indexes is defined in terms of a golden section g equal to ({square root over (5xe2x88x921)})/2;
(c) an input module coupled to said indexer for writing said stream of N input elements into said element memory according to said sequence of input indexes; and
(d) an output module coupled to said indexer for reading said stream of N output element from said element memory according to said sequence of output indexes.
The interleaving system can further comprise an index memory for storing a sequence of index offsets corresponding to the at least one of said sequences of indexes.
Alternatively, the indexer comprises an index memory for storing the at least one of said sequences of indexes. Another alternative is for the indexer to comprise:
(i) an index memory for storing a sequence of input index offsets; and
(ii) a nominal index generator coupled to said index memory for generating a sequence of nominal input indexes;
wherein the indexer generates the sequence of input indexes by adding said sequence of input index offsets to said sequence of nominal input indexes.
Yet another alternative is for the indexer to comprise:
(i) an index memory for storing a sequence of output index offsets;
(ii) a nominal index generator coupled to said index memory for generating a sequence of nominal output indexes;
wherein the indexer generates the sequence of output indexes by adding said sequence of output index offsets to said sequence of nominal output indexes.
In a first embodiment of this invention, a golden relative prime interleaver is provided wherein the indexer generates the at least one of said sequences of indexes as a sequence i with elements defined as i(n)=s+np, modulo N, where s is a pre-selected integer starting index, p is an integer index increment which is prime relative to N, defined in terms of g, and n is an integer progressively rising from 0 to Nxe2x88x921. The indexer gives p a value close to a real value c=N(gm+j)/r, where m is a pre-selected non-zero integer, r is a non-zero integer defining a distance between any pair of input elements that are to be maximally spread, and j is a pre-selected integer modulo r. In determining the value of p, one approach is to round p to one of a pair of values immediately above and below c. Alternatively, the value of p is selected to maximize a minimum difference between pairs of interleaver indexes within i up to a pre-selected maximum number of elements. Yet another approach is to select the value of p so as to maximize a weighted sum of minimum differences between pairs of interleaver indexes within i for all numbers of elements from 2 up to a pre-selected maximum number of elements. Preferably, r=1, j=0 and m is a non-zero integer having an absolute value less than 10. It is also preferred to have one sequence of said sequences of indexes to rise from zero to Nxe2x88x921 by an index increment of 1. The golden relative prime interleavers are particularly attractive because they are simple to implement and require little or no additional processing and memory, compared to no interleaving.
In a second embodiment of this invention, a golden vector interleaver is provided, wherein the indexer comprises:
(i) a vector generator for generating a golden vector v with elements defined as v(n)=s+nc, modulo N, where s is a pre-selected real starting value, c is a real increment value defined in terms of g, and n is an integer progressively rising from 0 to Nxe2x88x921;
(ii) sorting means responsive to said vector generator for finding a sort vector z determined from a(n)=v(z(n)), for n=0 . . . Nxe2x88x921, where a contains the elements of v sorted in one of rising and descending orders; and
(iii) assigning means responsive to said sorting means for assigning the at least one of said sequences of indexes i with elements defined by one of i(n)=z(n) and i(z(n))=n, for n=0 . . . Nxe2x88x921.
In one aspect of this second embodiment, a dithered golden vector interleaver is provided, wherein the vector generator uses a dither vector d with an n""th real dithering component d(n) of a prescribed distribution D for generating said golden vector such that v(n)=s+nc+d(n), modulo N. Preferably, c=N(gm+j)/r, where m is a pre-selected non-zero integer, r is a non-zero integer defining a distance between any pair of input elements that are to be maximally spread, and j is a pre-selected integer modulo r. Alternatively, the value of c is rounded to one of a pair of integer values immediately above and below the real value of N(gm+j)/r. Preferably, r=1,j=0 and m is a non-zero integer having an absolute value less than 10. It is also preferred to have one of said sequences of indexes rise from zero to Nxe2x88x921 by an index increment of 1. The dithered golden vector interleaver has the desirable spreading properties of the golden vector interleaver, but also has the randomness found beneficial for Turbo-codes.
In a practical embodiment of this invention, at least one interleaving system forms part of a tail-biting Turbo-code encoder comprising a plurality of tail-biting systematic convolutional encoders operating in parallel, wherein each of said at least one interleaving system is positioned at an input of at least one of said plurality of tail-biting systematic convolutional encoders.
In another practical embodiment of this invention, at least one interleaving system forms part of a Turbo-code encoder comprising a plurality of systematic convolutional encoders operating in parallel, wherein each of said at least one interleaving system is positioned at an input of at least one of said plurality of systematic convolutional encoders.
In another aspect of the present invention, there is provided an interleaving method for rearranging a stream of N input elements into a stream of N output elements, said interleaving method comprising the steps of:
(a) generating a sequence of input indexes and a sequence of output indexes, wherein at least one of said sequences of indexes is defined in terms of a golden section g equal to ({square root over (5xe2x88x921)})/2;
(b) writing said stream of N input elements into an element memory according to said sequence of input indexes; and
(c) reading said stream of N output element from said element memory according to said sequence of output indexes.
Alternative embodiments of this method are provided bearing similar limitations as those provided for the interleaving system defined above.